Computer networks have become critical to today's society. Their importance is reflected not only in the number of elements (such as servers, clients, hubs, routers and gateways) that are coupled together to form a network, but also in the varied and complex ways those elements are interconnected. Undisputably the most widely recognized example of a complex, distributed computer network is the Internet, which is responsible for interconnecting countless subnets and individual servers and clients.
As networks have become more complex, network configuration and management have likewise become more automated and standardized. Network configuration involves informing the various elements of their physical or logical connections (“links”) with one another such that optimal routes for information flow through the network can be defined. Network management involves, among other things, monitoring the links such that optimal routes can be redefined if new elements or links are introduced or if an active route is lost (perhaps due to element or link failure). The Internet works as well as it does in part because it has the ability to route around communications failures.
A comprehensive and standard protocol, the Border Gateway Protocol (BGP), has been developed expressly for routing. According to BGP, certain routers in the network periodically share, or “advertise,” information (called Router Information Base, or RIB, data) among themselves so they can keep track of each others' connections and thereby define the optimal routes. BGP is properly classified as a path vector routing protocol.
BGP allows networks to be compartmentalized to simplify routing. One concept designed into BGP is that of the Autonomous System, or AS. An AS is a collection of interconnected and cooperating network elements that can function independent of outside influence. BGP is employed both within ASs (so-called “internal” BGP, or IBGP) and between ASs that are coupled together (so-called “external” BGP, or EBGP). When viewed from a very high level, this feature of EBGP allows the ASs that make up a large network to be abstracted as single entities and managed as such.
EBGP is designed to deal with equipment or link failures. Once a border gateway router detects the loss of an active route, it sets about testing alternative routes through the network in an order that is determined at least in part by the speed of the alternative routes. It tests the alternative routes sent to it by neighboring border gateway routers. Thus, the loss of an active route can precipitate a substantial “conversation” among the border gateway routers as they try to work around the loss by converging on an optimal alternative route.
Unfortunately, BGP lacks a mechanism for diagnosing the cause underlying the loss. Lacking a diagnosis, the iterative testing process is ill-informed, resulting in the unnecessary consumption of time and network bandwidth as fruitless alternative routes are tested. What is needed in the art is a faster way to converge on an optimal alternative route upon the loss of an active route.